home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 551-575 / disk_556 / scheme2c / scheme-src.lzh / scrt / heap.h < prev    next >
C/C++ Source or Header  |  1991-10-11  |  16KB  |  424 lines
  1. /* SCHEME->C */
  2.  
  3. /*              Copyright 1989 Digital Equipment Corporation
  4.  *                         All Rights Reserved
  5.  *
  6.  * Permission to use, copy, and modify this software and its documentation is
  7.  * hereby granted only under the following terms and conditions.  Both the
  8.  * above copyright notice and this permission notice must appear in all copies
  9.  * of the software, derivative works or modified versions, and any portions
  10.  * thereof, and both notices must appear in supporting documentation.
  11.  *
  12.  * Users of this software agree to the terms and conditions set forth herein,
  13.  * and hereby grant back to Digital a non-exclusive, unrestricted, royalty-free
  14.  * right and license under any changes, enhancements or extensions made to the
  15.  * core functions of the software, including but not limited to those affording
  16.  * compatibility with other hardware or software environments, but excluding
  17.  * applications which incorporate this software.  Users further agree to use
  18.  * their best efforts to return to Digital any such changes, enhancements or
  19.  * extensions that they make and inform Digital of noteworthy uses of this
  20.  * software.  Correspondence should be provided to Digital at:
  21.  * 
  22.  *                       Director of Licensing
  23.  *                       Western Research Laboratory
  24.  *                       Digital Equipment Corporation
  25.  *                       100 Hamilton Avenue
  26.  *                       Palo Alto, California  94301  
  27.  * 
  28.  * This software may be distributed (but not offered for sale or transferred
  29.  * for compensation) to third parties, provided such third parties agree to
  30.  * abide by the terms and conditions of this notice.  
  31.  * 
  32.  * THE SOFTWARE IS PROVIDED "AS IS" AND DIGITAL EQUIPMENT CORP. DISCLAIMS ALL
  33.  * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  34.  * MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL DIGITAL EQUIPMENT
  35.  * CORPORATION BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
  36.  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  37.  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  38.  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  39.  * SOFTWARE.
  40. */
  41.  
  42. /* Import definitions */
  43.  
  44. #ifndef rusage
  45.  
  46. #ifdef apollo
  47. #include <sys/time.h>
  48. #else
  49. #ifdef SPARC
  50. #include <sys/time.h>
  51. #else
  52. #ifdef SUN3
  53. #include <sys/time.h>
  54. #else
  55. #ifndef SYSV
  56. #include <time.h>
  57. #endif
  58. #endif
  59. #endif
  60. #endif
  61.  
  62. #ifndef NO_RUSAGE
  63. #include <sys/resource.h>
  64. #endif
  65.  
  66. #endif
  67.  
  68. /* This module implements the object storage storage system for SCHEME->C.
  69.  
  70.    Unlike most Lisp systems, it is not intended that SCHEME->C provide a
  71.    "one language" environment divorced from other programming languages.
  72.    Instead, it is intended that SCHEME->C co-exist with other languages
  73.    and share their development tools and runtime environment.
  74.  
  75.    Nor, is it intended that SCHEME->C have detailed knowledge and intimate
  76.    control over the hardware.  Instead of generating actual instructions,
  77.    it generates C intermediate language.
  78.  
  79.    By adhering to these two design goals, SCHEME->C can be a powerful tool
  80.    for delivering Lisp based technology to non-Lisp environments.  However,
  81.    these design goals also place some significant constraints on the design
  82.    of the storage system.  For example:
  83.  
  84.    1.  The system must tolerate both Scheme and non-Scheme storage and
  85.        data types.
  86.  
  87.    2.  The system will not have any control over register allocation or
  88.        instruction sequences.
  89.  
  90.    3.  In examining register or stack contents, one can make a statement that
  91.        something is not a pointer, but one cannot say that something is a
  92.        pointer.  At best, one can say that it looks exactly like a pointer.
  93.  
  94.    Given these constraints, a conventional "stop-and-copy" garbage collector
  95.    cannot be used.  Instead, a storage allocation method called
  96.    "mostly-copying" is used (see WRL Research Report 88/2, Compacting Garbage
  97.    Collection with Ambiguous Roots).
  98.  
  99.    In its simplist form, the algorithm works as follows.  The heap is divided
  100.    into pages (which need not be the same size as the processor's page).
  101.    Objects are allocated entirely within a page, or in a dedicated set of
  102.    pages.  When half the storage in the heap has been allocated, the garbage
  103.    collector is invoked.
  104.  
  105.    Garbage collection is divided into three phases.  The first is the a copy
  106.    phase similar to that of the Minsky-Fenichel-Yochelson-Chaeny-Arnborg
  107.    collector.  Items will be copied from the oldspace (pages in the current
  108.    generation) to the newspace (pages in the next generation).  Indirect
  109.    pointers to new objects will be placed in the old objects, but pointers
  110.    to new objects are never stored in new objects.
  111.    
  112.    During this phase, the contents of continuations (including the current
  113.    continuation which is in the registers and the stack) get special
  114.    processing.  Each word in them is examined to see if it might be a pointer.
  115.    If it is a pointer, then the object that it points to is copied, and the
  116.    page is marked as locked.
  117.  
  118.    Thus at the end of the phase, all accessibile storage has been copied, and
  119.    all pointers are indirect through the old space.  All pages which have items
  120.    which must be left in place are marked as locked.
  121.  
  122.    The next phase is the correction phase which turns all indirect pointers
  123.    into their correct values.  At the end of this phase, all pointers will
  124.    point to the correct place, but items which were locked will be located in
  125.    the newspace.
  126.  
  127.    The final phase is the copy back phase where items that are locked are
  128.    copied back from the newspace to their correct position in the locked
  129.    pages.  At this time, locked pages are unlocked and promoted to newspace.
  130.  
  131.    At this point, garbage collection is done and the generation number is
  132.    advanced.  As with the classical "stop-and-copy" algorithm, the time used
  133.    is proportional to the amount of storage retained, rather than the total
  134.    amount of storage.  It needs somewhat more storage as it must retain locked
  135.    pages, and has duplicate copies of items of locked pages.
  136.  
  137.    In order to avoid repeated copying of retained data, the collector
  138.    implements a generational version of the algorithm.  Objects that survive
  139.    a collection are retained and not moved until more than SCLIMIT of the heap
  140.    is allocated following a collection.  At this point, the entire heap is
  141.    collected.
  142.  
  143.    A few simple changes to the previously described algorithm result in a
  144.    generational collector.  Even generation numbers represent retained storage
  145.    and storage is always allocated out of an odd numbered generation when the
  146.    user program is executing.  During garbage collection, all retained
  147.    objects in the odd generation are copied into a new even numbered space.
  148.    During this copy phase, pointers into an object in an even numbered space
  149.    need not be followed.  A total collection is done by changing the space
  150.    number on all even numbered pages to the current odd generation and then
  151.    doing a collection.
  152.  
  153.    In order for a generational scheme to work, all stores of pointers to new
  154.    objects in old pages must be detected.  This is done by explicit checks
  155.    in:  SET-CAR!, SET-CDR!, VECTOR-SET!, SET!, SET-TOP-LEVEL-VALUE!, PUTPROP,
  156.    and SCHEME-TSCP-SET!.  While at first glance, explicit checks seem a slow
  157.    way of doing things, the reduction in copying more than makes up for them.
  158.  
  159.    The garbage collector may be configured by the user setting any of the
  160.    following environment variables:
  161.  
  162.     name:     range:        default:    action:
  163.  
  164.        SCHEAP     [1:64]        4        Number of megabytes to allocate
  165.                         for the heap (total).
  166.  
  167.     SCLIMIT     [10:45]    33        Cause of total collection of
  168.                         the heap when more than this %
  169.                         of the heap is allocated
  170.                         following a generational
  171.                         collection.
  172.  
  173.     SCGCINFO [0:2]        0        C boolean indicating that
  174.                         garbage collection statistics
  175.                         should be printed on stderr.
  176.  
  177.                         When set to 2, additional
  178.                         debugging information is
  179.                         printed and additional tests
  180.                         are done.
  181. */
  182.  
  183. /* Page related definitions.  The page size is defined as a power of 2, where
  184.    2**PAGEPOWER = PAGEBYTES.
  185. */
  186.  
  187. #define PAGEPOWER    9        /* 512 bytes/page */
  188. #define PAGEBYTES    (1<<PAGEPOWER)
  189. #define PAGEWORDS    (PAGEBYTES/4)
  190. #define ONEMB        1048576
  191. #define PAGEBIT        PAGEPOWER
  192. #define PAGEBITLEN    (32-PAGEPOWER)
  193.  
  194. /* Page number to address conversion is handled by the following defines */
  195.  
  196. #define ADDRESS_PAGE( adr )   ((int) (((unsigned)(adr)) >> PAGEBIT))
  197. #define PAGE_ADDRESS( page )  ((page) << PAGEBIT)
  198. #define ADDRESS_OFFSET( adr ) (((int)(adr)) & (PAGEBYTES-1))
  199.  
  200. /* Each page in the pool has the following flags associated with it:
  201.    
  202.     PAGEGENERATION    generation number associated with the page.  Even
  203.             numbered generations are objects that survived a
  204.             garbage collection.  Odd numbered generations are
  205.             where storage is allocated during the execution of the
  206.             user's program.
  207.  
  208.     PAGETYPE    tag field indicating the type of data stored in the
  209.             page.  It is either PAIRTAG, EXTENDEDTAG, or
  210.             BIGEXTENDEDTAG.
  211.  
  212.     PAGELOCK    boolean indicating whether or not the page is locked
  213.             by the garbage collector.
  214.  
  215.     PAGELINK    next page (or 0) of the lock list whose head is kept in
  216.             LOCKLIST, and length in LOCKCNT (only during gc).
  217.                 -or-
  218.             OKTOSET or ~OKTOSET (-1 or 0) indicating status of
  219.             a just allocated page (value of INITIALLINK).
  220.                 -or-
  221.             next page (or -1) of the GENLIST, whose head is kept
  222.             in GENLIST.  This list contains all pages in older
  223.             generations that might contain a pointer to a newer
  224.             generation.
  225.  
  226.             If this value is non-zero, then it is possible to set
  227.             pointers in the page without going through
  228.             sc_setgeneration.
  229.  
  230.    It is possible to pack these fields into 1-2 words, but this has not been
  231.    done.
  232.  
  233.    Objects which are longer than one page are allocated on an integral number
  234.    of pages.  Pages other than the head are marked with a BIGEXTENDEDTAG in
  235.    pagetype field to indicate that they are related to the previous page.
  236.  
  237.    CURRENT_GENERATION holds the generation number that is presently being
  238.    allocated.  NEXT_GENERATION holds the obvious during garbage collection.
  239. */
  240.  
  241. extern int  *sc_pagegeneration,
  242.         *sc_pagetype,
  243.         *sc_pagelock,
  244.         *sc_pagelink,
  245.         sc_initiallink,
  246.         sc_locklist,
  247.         sc_genlist,
  248.         sc_lockcnt,
  249.         sc_current_generation,
  250.         sc_next_generation;
  251.  
  252. #define INC_GENERATION( g ) (g + 1)  /* 1 collection/second will take over 32
  253.                     years to overflow g */
  254. #define NEXTPAGE( page ) ((page==sc_lastheappage) ? sc_firstheappage : page+1)
  255. #define BIGEXTENDEDTAG -1
  256. #define OKTOSET -1
  257.  
  258. extern int  sc_firstheappage,        /* first page in the Scheme heap */
  259.         sc_lastheappage,        /* last page in the Scheme heap  */
  260.         sc_limit,            /* % of heap allocated after collecton
  261.                        that forces total collection */
  262.         sc_freepage,        /* Free page index */
  263.         sc_heappages,        /* # of pages in the Scheme heap */
  264.         sc_allocatedheappages,    /* # of pages currently allocated */
  265.         *sc_firstheapp,        /* ptr to first word in the heap */
  266.         *sc_lastheapp;        /* ptr to last word in the heap */
  267.  
  268. /* In order to speed up allocation of CONS cells, blocks of potential CONS
  269.    cells are preallocated.  CONSP points to the next free cell, and CONSCNT
  270.    is the number of free cells left.
  271. */
  272.  
  273. extern int  sc_conscnt;
  274. extern SCP  sc_consp;
  275.  
  276. /* In order to speed up allocation of extended objects, EXTOBJWORDS is the
  277.    number of words available in the current page pointed to by EXTOBJP.
  278.    EXTWASTE keeps track of the number of words lost because of page alignment
  279.    problems.  When only a part of the page is used, the first unused word is
  280.    marked with ENDOFPAGE.
  281. */
  282.  
  283. extern int  sc_extobjwords,
  284.         sc_extwaste;
  285. extern SCP  sc_extobjp;
  286.  
  287. #define ENDOFPAGE 0xAAAAAAAA
  288.  
  289. /* Some implementations require extended storage always be allocated so that
  290.    double objects in it are on double word boundaries (addr mod 8 = 0).  This
  291.    is handled by the following define that is used to force pointer alignment.
  292. */
  293.  
  294. #ifdef DOUBLE_ALIGN
  295. #define ODD_EXTOBJP( e )  if  ((e) && sc_extobjwords &&\
  296.                    (sc_extobjwords & 1) == 0)  {\
  297.                         sc_extobjp->unsi.gned = WORDALIGNTAG;\
  298.                         sc_extobjp = (SCP)(((int*)sc_extobjp)+1);\
  299.                         sc_extobjwords = sc_extobjwords-1;\
  300.                    }
  301. #define EVEN_EXTOBJP( e )  if  ((e) && sc_extobjwords & 1)  {\
  302.                         sc_extobjp->unsi.gned = WORDALIGNTAG;\
  303.                         sc_extobjp = (SCP)(((int*)sc_extobjp)+1);\
  304.                         sc_extobjwords = sc_extobjwords-1;\
  305.                    }
  306. #endif
  307. #ifndef DOUBLE_ALIGN
  308. #define ODD_EXTOBJP( e )
  309. #define EVEN_EXTOBJP( e )
  310. #endif
  311.  
  312. /* A running total of garbage collection resource usage in kept in GCRU.
  313.    
  314.    Garbage collection statistics are printed on stderr following each
  315.    collection when SCGCINFO is true (set by the environment variable SCGCINFO,
  316.    or by the command line flag -scgc, default = 0).
  317. */
  318.  
  319. extern int  sc_gcinfo;
  320.  
  321. /* Garbage collection and call-with-current-continuation need to know the
  322.    base of the stack, i.e. the value of the stack pointer when the stack is
  323.    empty.  It is computed at initialization time and stored in SC_STACKBASE.
  324.    STACKPTR is the address of the current top of stack.
  325. */
  326.  
  327. extern int  *sc_stackbase;
  328.  
  329. #ifdef MIPS
  330. #define STACKPTR sc_processor_register( 29 )
  331. #endif
  332.  
  333. #ifdef TITAN
  334. extern int  *zzReadRegister();
  335. #define STACKPTR (zzReadRegister( 63 )+1)
  336. #endif
  337.  
  338. #ifdef VAX
  339. #define STACKPTR sc_processor_register( 14 )
  340. #endif
  341.  
  342. #ifdef APOLLO
  343. #define STACKPTR sc_processor_register( 7 )
  344. #endif
  345.  
  346. #ifdef PRISM
  347. extern int* prism_stack_frame(void);
  348. #define STACKPTR prism_stack_frame()
  349. #endif
  350.  
  351. #ifdef I386
  352. #define STACKPTR sc_processor_register( 4 )
  353. #endif
  354.  
  355. #ifdef SPARC
  356. #define STACKPTR sc_processor_register( 0 )
  357. #endif
  358.  
  359. #ifdef    AMIGA
  360. #include <dos.h>
  361. #define STACKPTR getreg(15)
  362. #endif
  363.  
  364. #ifdef SUN3
  365. #define STACKPTR sc_processor_register( 15 )
  366. #endif
  367.  
  368. /* Some objects require cleanup actions when they are freed.  For example,
  369.    when a file port is recovered, the corresponding file needs to be closed.
  370.    Such objects are noted by the procedure (WHEN-UNREFERENCED object action),
  371.    where object is any Scheme object and action is either #F indicating that
  372.    nothing should be done, or a procedure that takes one argument.  When a
  373.    procedure is supplied, it will be called when a garbage collection occurs
  374.    and there are no references to that object.  In order to implement this
  375.    function, the runtime system will keep two alists, SC_WHENFREED and
  376.    SC_FREED.  The first list is those items requiring cleanup when they
  377.    become free, and the second list is those items freed that require
  378.    cleanup now.
  379. */
  380.  
  381. extern TSCP  sc_whenfreed,
  382.          sc_freed;
  383.  
  384. /* A Scheme program can register a callback with the garbage collector that
  385.    will be called following each collection.  This is done by setting the
  386.    value of AFTER-COLLECT to a procedure that takes three arguments:  the
  387.    heap size in bytes, the current allocation in bytes, and the percent of
  388.    allocation that will force a total collection.
  389. */
  390.  
  391. extern TSCP  sc_after_2dcollect_v;
  392.  
  393. /* The procedural interfaces to this module are:  */
  394.  
  395. extern int  *sc_processor_register();
  396.  
  397. extern TSCP  sc_my_2drusage_v;
  398.  
  399. extern TSCP  sc_my_2drusage();
  400.  
  401. extern TSCP  sc_collect_2drusage_v;
  402.  
  403. extern TSCP  sc_collect_2drusage();
  404.  
  405. extern TSCP  sc_collect_v;
  406.  
  407. extern TSCP  sc_collect();
  408.  
  409. extern TSCP  sc_collect_2dall_v;
  410.  
  411. extern TSCP  sc_collect_2dall();
  412.  
  413. extern TSCP  sc_setgeneration();
  414.  
  415. extern SCP  sc_allocateheap();
  416.  
  417. extern TSCP  sc_makefloat32();
  418.  
  419. extern TSCP  sc_makefloat64();
  420.  
  421. extern TSCP  sc_cons_v;
  422.  
  423. extern TSCP  sc_cons();
  424.